//
//  19. 删除链表的倒数第N个节点.swift
//  Top600
//
//  Created by rjb on 2021/7/27.
//

import Foundation

public class ListNode {
    public var val:Int
    public var next:ListNode?
    public init(_ val:Int) {
        self.val = val
        self.next = nil
    }
}

class Solution19 {
    // 特别注意：删除节点时，一定要区分头节点
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let newHead = ListNode(-1)
        newHead.next = head
        
        var p1: ListNode? = newHead
        var p2: ListNode? = newHead
        var k = n // 2
        while p2 != nil {
            if k < 0  {
                p1 = p1?.next
            } else {
                k -= 1
            }
            p2 = p2?.next
        }
        p1?.next = p1?.next?.next
        return newHead.next
    }
    static func test() {
        let node1 = ListNode(1)
        let node2 = ListNode(2)
        let node3 = ListNode(3)
        let node4 = ListNode(4)
        let node5 = ListNode(5)
//
        node1.next = node2
        node2.next = node3
        node3.next = node4
        node4.next = node5
        let solution = Solution19()
        let result = solution.removeNthFromEnd(node1, 2)
        print(result)
    }
}
